home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 14 / CU Amiga Magazine's Super CD-ROM 14 (1997)(EMAP Images)(GB)(Track 1 of 3)[!][issue 1997-09].iso / CUCD / Programming / Mesa-2.2 / src-glu / polytest.c < prev    next >
Encoding:
C/C++ Source or Header  |  1996-09-27  |  25.9 KB  |  1,020 lines
  1. /* $Id: polytest.c,v 1.1 1996/09/27 01:19:39 brianp Exp $ */
  2.  
  3. /*
  4.  * Mesa 3-D graphics library
  5.  * Version:  2.0
  6.  * Copyright (C) 1995-1996  Brian Paul
  7.  *
  8.  * This library is free software; you can redistribute it and/or
  9.  * modify it under the terms of the GNU Library General Public
  10.  * License as published by the Free Software Foundation; either
  11.  * version 2 of the License, or (at your option) any later version.
  12.  *
  13.  * This library is distributed in the hope that it will be useful,
  14.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16.  * Library General Public License for more details.
  17.  *
  18.  * You should have received a copy of the GNU Library General Public
  19.  * License along with this library; if not, write to the Free
  20.  * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  21.  */
  22.  
  23.  
  24. /*
  25.  * $Log: polytest.c,v $
  26.  * Revision 1.1  1996/09/27 01:19:39  brianp
  27.  * Initial revision
  28.  *
  29.  */
  30.  
  31.  
  32. /*
  33.  * This file is part of the polygon tesselation code contributed by
  34.  * Bogdan Sikorski
  35.  */
  36.  
  37.  
  38. #include <math.h>
  39. #include <stdlib.h>
  40. #include "gluP.h"
  41. #include "tess.h"
  42.  
  43.  
  44.  
  45. static GLenum store_polygon_as_contour(GLUtriangulatorObj *);
  46. static void free_current_polygon(tess_polygon *);
  47. static void prepare_projection_info(GLUtriangulatorObj *);
  48. static GLdouble twice_the_polygon_area(tess_vertex *,tess_vertex *);
  49. static GLenum verify_edge_vertex_intersections(GLUtriangulatorObj *);
  50. void tess_find_contour_hierarchies(GLUtriangulatorObj *);
  51. static GLenum test_for_overlapping_contours(GLUtriangulatorObj *);
  52. static GLenum contours_overlap(tess_contour *, tess_polygon *);
  53. static GLenum is_contour_contained_in(tess_contour *,tess_contour *);
  54. static void add_new_exterior(GLUtriangulatorObj *,tess_contour *);
  55. static void add_new_interior(GLUtriangulatorObj *,tess_contour *,
  56.     tess_contour *);
  57. static void add_interior_with_hierarchy_check(GLUtriangulatorObj *,
  58.     tess_contour *,tess_contour *);
  59. static void reverse_hierarchy_and_add_exterior(GLUtriangulatorObj *,
  60.     tess_contour *,tess_contour *);
  61. static GLboolean point_in_polygon(tess_contour *,GLdouble,GLdouble);
  62. static void shift_interior_to_exterior(GLUtriangulatorObj *,tess_contour *);
  63. static void add_exterior_with_check(GLUtriangulatorObj *,tess_contour *,
  64.     tess_contour *);
  65. static GLenum cut_out_hole(GLUtriangulatorObj *,tess_contour *,
  66.     tess_contour *);
  67. static GLenum merge_hole_with_contour(GLUtriangulatorObj *,
  68.     tess_contour *,tess_contour *,tess_vertex *,
  69.     tess_vertex *);
  70.  
  71. static GLenum
  72. find_normal(GLUtriangulatorObj *tobj)
  73. {
  74.     tess_polygon *polygon=tobj->current_polygon;
  75.     tess_vertex *va,*vb,*vc;
  76.     GLdouble A,B,C;
  77.     GLdouble A0,A1,A2,B0,B1,B2;
  78.  
  79.     va=polygon->vertices;
  80.     vb=va->next;
  81.     A0=vb->location[0]-va->location[0];
  82.     A1=vb->location[1]-va->location[1];
  83.     A2=vb->location[2]-va->location[2];
  84.     for(vc=vb->next;vc!=va;vc=vc->next)
  85.     {
  86.         B0=vc->location[0]-va->location[0];
  87.         B1=vc->location[1]-va->location[1];
  88.         B2=vc->location[2]-va->location[2];
  89.         A=A1*B2-A2*B1;
  90.         B=A2*B0-A0*B2;
  91.         C=A0*B1-A1*B0;
  92.         if(fabs(A)>EPSILON || fabs(B)>EPSILON || fabs(C)>EPSILON)
  93.         {
  94.             polygon->A=A;
  95.             polygon->B=B;
  96.             polygon->C=C;
  97.             polygon->D= -A*va->location[0]-B*va->location[1]-C*va->location[2];
  98.             return GLU_NO_ERROR;
  99.         }
  100.     }
  101.     tess_call_user_error(tobj,GLU_TESS_ERROR7);
  102.     return GLU_ERROR;
  103. }
  104.  
  105. void
  106. tess_test_polygon( GLUtriangulatorObj *tobj )
  107. {
  108.     tess_polygon *polygon=tobj->current_polygon;
  109.  
  110.     /* any vertices defined? */
  111.     if(polygon->vertex_cnt<3)
  112.     {
  113.         free_current_polygon(polygon);
  114.         return;
  115.     }
  116.     /* wrap pointers */
  117.     polygon->last_vertex->next=polygon->vertices;
  118.     polygon->vertices->previous=polygon->last_vertex;
  119.     /* determine the normal */
  120.     if(find_normal(tobj)==GLU_ERROR)
  121.         return;
  122.     /* compare the normals of previously defined contours and this one */
  123.     /* first contour define ? */
  124.     if(tobj->contours==NULL)
  125.     {
  126.         tobj->A=polygon->A;
  127.         tobj->B=polygon->B;
  128.         tobj->C=polygon->C;
  129.         tobj->D=polygon->D;
  130.         /* determine the best projection to use */
  131.         if(fabs(polygon->A) > fabs(polygon->B))
  132.             if(fabs(polygon->A) > fabs(polygon->C))
  133.                 tobj->projection=OYZ;
  134.             else
  135.                 tobj->projection=OXY;
  136.         else
  137.             if(fabs(polygon->B) > fabs(polygon->C))
  138.                 tobj->projection=OXZ;
  139.             else
  140.                 tobj->projection=OXY;
  141.     }
  142.     else
  143.     {
  144.         GLdouble a[3],b[3];
  145.         tess_vertex *vertex=polygon->vertices;
  146.  
  147.         a[0]=tobj->A;
  148.         a[1]=tobj->B;
  149.         a[2]=tobj->C;
  150.         b[0]=polygon->A;
  151.         b[1]=polygon->B;
  152.         b[2]=polygon->C;
  153.  
  154.         /* compare the normals */
  155.         if( fabs(a[1]*b[2]-a[2]*b[1]) > EPSILON ||
  156.             fabs(a[2]*b[0]-a[0]*b[2]) > EPSILON ||
  157.             fabs(a[0]*b[1]-a[1]*b[0]) > EPSILON)
  158.         {
  159.             /* not coplanar */
  160.             tess_call_user_error(tobj,GLU_TESS_ERROR9);
  161.             return;
  162.         }
  163.         /* the normals are parallel - test for plane equation */
  164.         if(fabs(a[0]*vertex->location[0]+a[1]*vertex->location[1]+
  165.             a[2]*vertex->location[2]+tobj->D) > EPSILON)
  166.         {
  167.             /* not the same plane */
  168.             tess_call_user_error(tobj,GLU_TESS_ERROR9);
  169.             return;
  170.         }
  171.     }
  172.     prepare_projection_info(tobj);
  173.     if(verify_edge_vertex_intersections(tobj)==GLU_ERROR)
  174.         return;
  175.     if(test_for_overlapping_contours(tobj)==GLU_ERROR)
  176.         return;
  177.     if(store_polygon_as_contour(tobj)==GLU_ERROR)
  178.         return;
  179. }
  180.  
  181. static GLenum test_for_overlapping_contours(GLUtriangulatorObj *tobj)
  182. {
  183.     tess_contour *contour;
  184.     tess_polygon *polygon;
  185.  
  186.     polygon=tobj->current_polygon;
  187.     for(contour=tobj->contours;contour!=NULL;contour=contour->next)
  188.         if(contours_overlap(contour,polygon)!=GLU_NO_ERROR)
  189.         {
  190.             tess_call_user_error(tobj,GLU_TESS_ERROR5);
  191.             return GLU_ERROR;
  192.         }
  193.     return GLU_NO_ERROR;
  194. }
  195.  
  196. static GLenum store_polygon_as_contour(GLUtriangulatorObj *tobj)
  197. {
  198.     tess_polygon *polygon=tobj->current_polygon;
  199.     tess_contour *contour=tobj->contours;
  200.  
  201.     /* the first contour defined */
  202.     if(contour==NULL)
  203.     {
  204.         if((contour=(tess_contour *)malloc(
  205.             sizeof(tess_contour)))==NULL)
  206.         {
  207.             tess_call_user_error(tobj,GLU_OUT_OF_MEMORY);
  208.             free_current_polygon(polygon);
  209.             return GLU_ERROR;
  210.         }
  211.         tobj->contours=tobj->last_contour=contour;
  212.         contour->next=contour->previous=NULL;
  213.     }
  214.     else
  215.     {
  216.         if((contour=(tess_contour *)malloc(
  217.             sizeof(tess_contour)))==NULL)
  218.         {
  219.             tess_call_user_error(tobj,GLU_OUT_OF_MEMORY);
  220.             free_current_polygon(polygon);
  221.             return GLU_ERROR;
  222.         }
  223.         contour->previous=tobj->last_contour;
  224.         tobj->last_contour->next=contour;
  225.         tobj->last_contour=contour;
  226.         contour->next=NULL;
  227.     }
  228.     /* mark all vertices in new contour as not special */
  229.     /* and all are boundary edges */
  230.     {
  231.         tess_vertex *vertex;
  232.         GLuint vertex_cnt,i;
  233.  
  234.         for(vertex=polygon->vertices , i=0 , vertex_cnt=polygon->vertex_cnt;
  235.             i<vertex_cnt;
  236.             vertex=vertex->next , i++)
  237.         {
  238.             vertex->shadow_vertex=NULL;
  239.             vertex->edge_flag=GL_TRUE;
  240.         }
  241.     }
  242.     contour->vertex_cnt=polygon->vertex_cnt;
  243.     contour->area=polygon->area;
  244.     contour->orientation=polygon->orientation;
  245.     contour->type=GLU_UNKNOWN;
  246.     contour->vertices=polygon->vertices;
  247.     contour->last_vertex=polygon->last_vertex;
  248.     polygon->vertices=polygon->last_vertex=NULL;
  249.     polygon->vertex_cnt=0;
  250.     ++(tobj->contour_cnt);
  251.     return GLU_NO_ERROR;
  252. }
  253.  
  254. static void free_current_polygon(tess_polygon *polygon)
  255. {
  256.     tess_vertex *vertex,*vertex_tmp;
  257.  
  258.     /* free current_polygon structures */
  259.     for(vertex=polygon->vertices;vertex!=polygon->last_vertex;)
  260.     {
  261.         vertex_tmp=vertex->next;
  262.         free(vertex);
  263.         vertex=vertex_tmp;
  264.     }
  265.     polygon->vertices=polygon->last_vertex=NULL;
  266.     polygon->vertex_cnt=0;
  267. }
  268.  
  269. static void prepare_projection_info(GLUtriangulatorObj *tobj)
  270. {
  271.     tess_polygon *polygon=tobj->current_polygon;
  272.     tess_vertex *vertex,*last_vertex_ptr;
  273.     GLdouble area;
  274.  
  275.     last_vertex_ptr=polygon->last_vertex;
  276.     switch(tobj->projection)
  277.     {
  278.         case OXY:
  279.             for(vertex=polygon->vertices;vertex!=last_vertex_ptr;
  280.                 vertex=vertex->next)
  281.             {
  282.                 vertex->x=vertex->location[0];
  283.                 vertex->y=vertex->location[1];
  284.             }
  285.             last_vertex_ptr->x=last_vertex_ptr->location[0];
  286.             last_vertex_ptr->y=last_vertex_ptr->location[1];
  287.             break;
  288.         case OXZ:
  289.             for(vertex=polygon->vertices;vertex!=last_vertex_ptr;
  290.                 vertex=vertex->next)
  291.             {
  292.                 vertex->x=vertex->location[0];
  293.                 vertex->y=vertex->location[2];
  294.             }
  295.             last_vertex_ptr->x=last_vertex_ptr->location[0];
  296.             last_vertex_ptr->y=last_vertex_ptr->location[2];
  297.             break;
  298.         case OYZ:
  299.             for(vertex=polygon->vertices;vertex!=last_vertex_ptr;
  300.                 vertex=vertex->next)
  301.             {
  302.                 vertex->x=vertex->location[1];
  303.                 vertex->y=vertex->location[2];
  304.             }
  305.             last_vertex_ptr->x=last_vertex_ptr->location[1];
  306.             last_vertex_ptr->y=last_vertex_ptr->location[2];
  307.             break;
  308.     }
  309.     area=twice_the_polygon_area(polygon->vertices,polygon->last_vertex);
  310.     if(area >= 0.0)
  311.     {
  312.         polygon->orientation=GLU_CCW;
  313.         polygon->area=area;
  314.     }
  315.     else
  316.     {
  317.         polygon->orientation=GLU_CW;
  318.         polygon->area= -area;
  319.     }
  320. }
  321.  
  322. static GLdouble twice_the_polygon_area(tess_vertex *vertex,
  323.     tess_vertex *last_vertex)
  324. {
  325.     tess_vertex *next;
  326.     GLdouble area,x,y;
  327.  
  328.     area=0.0;
  329.     x=vertex->x;
  330.     y=vertex->y;
  331.     vertex=vertex->next;
  332.     for(; vertex!=last_vertex; vertex=vertex->next)
  333.     {
  334.         next=vertex->next;
  335.         area+=(vertex->x - x)*(next->y - y) - (vertex->y - y)*(next->x - x);
  336.     }
  337.     return area;
  338. }
  339.  
  340. /* test if edges ab and cd intersect */
  341. /* if not return GLU_NO_ERROR, else if cross return GLU_TESS_ERROR8, */
  342. /* else if adjacent return GLU_TESS_ERROR4 */
  343. static GLenum edge_edge_intersect(
  344.     tess_vertex *a,
  345.     tess_vertex *b,
  346.     tess_vertex *c,
  347.     tess_vertex *d)
  348. {
  349.     GLdouble denom,r,s;
  350.     GLdouble xba,ydc,yba,xdc,yac,xac;
  351.  
  352.     xba=b->x - a->x;
  353.     yba=b->y - a->y;
  354.     xdc=d->x - c->x;
  355.     ydc=d->y - c->y;
  356.     xac=a->x - c->x;
  357.     yac=a->y - c->y;
  358.     denom= xba*ydc - yba*xdc;
  359.     r = yac*xdc - xac*ydc;
  360.     /* parallel? */
  361.     if(fabs(denom) < EPSILON)
  362.     {
  363.         if(fabs(r) < EPSILON)
  364.         {
  365.             /* colinear */
  366.             if(fabs(xba) < EPSILON)
  367.             {
  368.                 /* compare the Y coordinate */
  369.                 if(yba > 0.0)
  370.                 {
  371.                     if((fabs(a->y - c->y)<EPSILON && fabs(c->y - b->y)<EPSILON)
  372.                         ||
  373.                         (fabs(a->y - d->y)<EPSILON && fabs(d->y - b->y)<EPSILON))
  374.                     return GLU_TESS_ERROR4;
  375.  
  376.                 }
  377.                 else
  378.                 {
  379.                     if((fabs(b->y - c->y)<EPSILON && fabs(c->y - a->y)<EPSILON)
  380.                         ||
  381.                         (fabs(b->y - d->y)<EPSILON && fabs(d->y - a->y)<EPSILON))
  382.                     return GLU_TESS_ERROR4;
  383.                 }
  384.             }
  385.             else
  386.             {
  387.                 /* compare the X coordinate */
  388.                 if(xba > 0.0)
  389.                 {
  390.                     if((fabs(a->x - c->x)<EPSILON && fabs(c->x - b->x)<EPSILON)
  391.                         ||
  392.                         (fabs(a->x - d->x)<EPSILON && fabs(d->x - b->x)<EPSILON))
  393.                     return GLU_TESS_ERROR4;
  394.                 }
  395.                 else
  396.                 {
  397.                     if((fabs(b->x - c->x)<EPSILON && fabs(c->x - a->x)<EPSILON)
  398.                         ||
  399.                         (fabs(b->x - d->x)<EPSILON && fabs(d->x - a->x)<EPSILON))
  400.                     return GLU_TESS_ERROR4;
  401.                 }
  402.             }
  403.         }
  404.         return GLU_NO_ERROR;
  405.     }
  406.     r /= denom;
  407.     s = (yac*xba - xac*yba) / denom;
  408.     /* test if one vertex lies on other edge */
  409.     if(((fabs(r) < EPSILON || (r < 1.0+EPSILON && r > 1.0-EPSILON)) &&
  410.         s > -EPSILON && s < 1.0+EPSILON) ||
  411.         ((fabs(s) < EPSILON || (s < 1.0+EPSILON && s > 1.0-EPSILON)) &&
  412.         r > -EPSILON && r < 1.0+EPSILON))
  413.     {
  414.         return GLU_TESS_ERROR4;
  415.     }
  416.     /* test for crossing */
  417.     if(r > -EPSILON && r < 1.0+EPSILON &&
  418.         s > -EPSILON && s < 1.0+EPSILON)
  419.     {
  420.         return GLU_TESS_ERROR8;
  421.     }
  422.     return GLU_NO_ERROR;
  423. }
  424.  
  425. static GLenum verify_edge_vertex_intersections(GLUtriangulatorObj *tobj)
  426. {
  427.     tess_polygon *polygon=tobj->current_polygon;
  428.     tess_vertex *vertex1,*last_vertex,*vertex2;
  429.     GLenum test;
  430.  
  431.     last_vertex=polygon->last_vertex;
  432.     vertex1=last_vertex;
  433.     for(vertex2=vertex1->next->next;
  434.         vertex2->next!=last_vertex;
  435.         vertex2=vertex2->next)
  436.     {
  437.         test=edge_edge_intersect(vertex1,vertex1->next,vertex2,
  438.             vertex2->next);
  439.         if(test!=GLU_NO_ERROR)
  440.         {
  441.             tess_call_user_error(tobj,test);
  442.             return GLU_ERROR;
  443.         }
  444.     }
  445.     for(vertex1=polygon->vertices;
  446.         vertex1->next->next!=last_vertex;
  447.         vertex1=vertex1->next)
  448.     {
  449.         for(vertex2=vertex1->next->next;
  450.             vertex2!=last_vertex;
  451.             vertex2=vertex2->next)
  452.         {
  453.             test=edge_edge_intersect(vertex1,vertex1->next,vertex2,
  454.                 vertex2->next);
  455.             if(test!=GLU_NO_ERROR)
  456.             {
  457.                 tess_call_user_error(tobj,test);
  458.                 return GLU_ERROR;
  459.             }
  460.         }
  461.     }
  462.     return GLU_NO_ERROR;
  463. }
  464.  
  465. static int area_compare(const void *a,const void *b)
  466. {
  467.     GLdouble area1,area2;
  468.  
  469.     area1=(*((tess_contour **)a))->area;
  470.     area2=(*((tess_contour **)b))->area;
  471.     if(area1 < area2)
  472.         return 1;
  473.     if(area1 > area2)
  474.         return -1;
  475.     return 0;
  476. }
  477.  
  478. void tess_find_contour_hierarchies(GLUtriangulatorObj *tobj)
  479. {
  480.     tess_contour **contours; /* dinamic array of pointers */
  481.     tess_contour *tmp_contour_ptr=tobj->contours;
  482.     GLuint cnt,i;
  483.     GLenum result;
  484.     GLboolean hierarchy_changed;
  485.  
  486.     /* any contours? */
  487.     if(tobj->contour_cnt < 2)
  488.     {
  489.         tobj->contours->type=GLU_EXTERIOR;
  490.         return;
  491.     }
  492.     if((contours=(tess_contour **)
  493.         malloc(sizeof(tess_contour *)*(tobj->contour_cnt)))==NULL)
  494.     {
  495.         tess_call_user_error(tobj,GLU_OUT_OF_MEMORY);
  496.         return;
  497.     }
  498.     for(tmp_contour_ptr=tobj->contours , cnt=0;
  499.         tmp_contour_ptr!=NULL;
  500.         tmp_contour_ptr=tmp_contour_ptr->next)
  501.         contours[cnt++]=tmp_contour_ptr;
  502.     /* now sort the contours in decreasing area size order */
  503.     qsort((void *)contours,(size_t)cnt,(size_t)sizeof(tess_contour *),area_compare);
  504.     /* we leave just the first contour - remove others from list */
  505.     tobj->contours=contours[0];
  506.     tobj->contours->next=tobj->contours->previous=NULL;
  507.     tobj->last_contour=tobj->contours;
  508.     tobj->contour_cnt=1;
  509.     /* first contour is the one with greatest area */
  510.     /* must be EXTERIOR */
  511.     tobj->contours->type=GLU_EXTERIOR;
  512.     tmp_contour_ptr=tobj->contours;
  513.     /* now we play! */
  514.     for(i=1;i<cnt;i++)
  515.     {
  516.         hierarchy_changed=GL_FALSE;
  517.         for(tmp_contour_ptr=tobj->contours;
  518.             tmp_contour_ptr!=NULL;
  519.             tmp_contour_ptr=tmp_contour_ptr->next)
  520.         {
  521.             if(tmp_contour_ptr->type==GLU_EXTERIOR)
  522.             {
  523.                 /* check if contour completely contained in EXTERIOR */
  524.                 result=is_contour_contained_in(tmp_contour_ptr,contours[i]);
  525.                 switch(result)
  526.                 {
  527.                     case GLU_INTERIOR:
  528.                         /* now we have to check if contour is inside interiors */
  529.                         /* or not */
  530.                         /* any interiors? */
  531.                         if(tmp_contour_ptr->next!=NULL &&
  532.                             tmp_contour_ptr->next->type==GLU_INTERIOR)
  533.                         {
  534.                             /* for all interior, check if inside any of them */
  535.                             /* if not inside any of interiors, its another */
  536.                             /* interior */
  537.                             /* or it may contain some interiors, then change */
  538.                             /* the contained interiors to exterior ones */
  539.                             add_interior_with_hierarchy_check(tobj,
  540.                                 tmp_contour_ptr,contours[i]);
  541.                         }
  542.                         else
  543.                         {
  544.                             /* not in interior, add as new interior contour */
  545.                             add_new_interior(tobj,tmp_contour_ptr,contours[i]);
  546.                         }
  547.                         hierarchy_changed=GL_TRUE;
  548.                         break;
  549.                     case GLU_EXTERIOR:
  550.                         /* ooops, the marked as EXTERIOR (contours[i]) is */
  551.                         /* actually an interior of tmp_contour_ptr */
  552.                         /*  reverse the local hierarchy */
  553.                         reverse_hierarchy_and_add_exterior(tobj,tmp_contour_ptr,
  554.                             contours[i]);
  555.                         hierarchy_changed=GL_TRUE;
  556.                         break;
  557.                     case GLU_NO_ERROR:
  558.                         break;
  559.                     default:
  560.                         abort();
  561.                 }
  562.             }
  563.             if(hierarchy_changed)
  564.                 break; /* break from for loop */
  565.         }
  566.         if(hierarchy_changed==GL_FALSE)
  567.         {
  568.             /* disjoint with all contours, add to contour list */
  569.             add_new_exterior(tobj,contours[i]);
  570.         }
  571.     }
  572.     free(contours);
  573. }
  574.  
  575. /* returns GLU_INTERIOR if inner is completey enclosed within outer */
  576. /* returns GLU_EXTERIOR if outer is completely enclosed within inner */
  577. /* returns GLU_NO_ERROR if contours are disjoint */
  578. static GLenum is_contour_contained_in(
  579.     tess_contour *outer,
  580.     tess_contour *inner)
  581. {
  582.     GLenum relation_flag;
  583.  
  584.     /* set relation_flag to relation of containment of first inner vertex */
  585.     /* regarding outer contour */
  586.     if(point_in_polygon(outer,inner->vertices->x,inner->vertices->y))
  587.         relation_flag=GLU_INTERIOR;
  588.     else
  589.         relation_flag=GLU_EXTERIOR;
  590.     if(relation_flag==GLU_INTERIOR)
  591.         return GLU_INTERIOR;
  592.     if(point_in_polygon(inner,outer->vertices->x,outer->vertices->y))
  593.         return GLU_EXTERIOR;
  594.     return GLU_NO_ERROR;
  595. }
  596.  
  597. static GLboolean point_in_polygon(
  598.     tess_contour *contour,
  599.     GLdouble x,
  600.     GLdouble y)
  601. {
  602.     tess_vertex *v1,*v2;
  603.     GLuint i,vertex_cnt;
  604.     GLdouble xp1,yp1,xp2,yp2;
  605.     GLboolean tst;
  606.  
  607.     tst=GL_FALSE;
  608.     v1=contour->vertices;
  609.     v2=contour->vertices->previous;
  610.     for(i=0 , vertex_cnt=contour->vertex_cnt;
  611.         i < vertex_cnt;
  612.         i++)
  613.     {
  614.         xp1=v1->x;
  615.         yp1=v1->y;
  616.         xp2=v2->x;
  617.         yp2=v2->y;
  618.         if ((((yp1<=y) && (y<yp2)) || ((yp2<=y)  && (y<yp1))) &&
  619.             (x < (xp2 - xp1) * (y - yp1) /  (yp2 - yp1) + xp1))
  620.                 tst = (tst==GL_FALSE ? GL_TRUE : GL_FALSE);
  621.         v2=v1;
  622.         v1=v1->next;
  623.     }
  624.     return tst;
  625. }
  626.  
  627. static GLenum contours_overlap(
  628.     tess_contour *contour,
  629.     tess_polygon *polygon)
  630. {
  631.     tess_vertex *vertex1,*vertex2;
  632.     GLuint vertex1_cnt,vertex2_cnt,i,j;
  633.     GLenum test;
  634.  
  635.     vertex1=contour->vertices;
  636.     vertex2=polygon->vertices;
  637.     vertex1_cnt=contour->vertex_cnt;
  638.     vertex2_cnt=polygon->vertex_cnt;
  639.     for(i=0; i<vertex1_cnt; vertex1=vertex1->next , i++)
  640.     {
  641.         for(j=0; j<vertex2_cnt; vertex2=vertex2->next , j++)
  642.             if((test=edge_edge_intersect(vertex1,vertex1->next,vertex2,
  643.                 vertex2->next))!=GLU_NO_ERROR)
  644.                 return test;
  645.     }
  646.     return GLU_NO_ERROR;
  647. }
  648.  
  649. static void add_new_exterior(
  650.     GLUtriangulatorObj *tobj,
  651.     tess_contour *contour)
  652. {
  653.     contour->type=GLU_EXTERIOR;
  654.     contour->next=NULL;
  655.     contour->previous=tobj->last_contour;
  656.     tobj->last_contour->next=contour;
  657.     tobj->last_contour=contour;
  658. }
  659.  
  660. static void add_new_interior(
  661.     GLUtriangulatorObj *tobj,
  662.     tess_contour *outer,
  663.     tess_contour *contour)
  664. {
  665.     contour->type=GLU_INTERIOR;
  666.     contour->next=outer->next;
  667.     contour->previous=outer;
  668.     if(outer->next!=NULL)
  669.         outer->next->previous=contour;
  670.     outer->next=contour;
  671.     if(tobj->last_contour==outer)
  672.         tobj->last_contour=contour;
  673. }
  674.  
  675. static void add_interior_with_hierarchy_check(
  676.     GLUtriangulatorObj *tobj,
  677.     tess_contour *outer,
  678.     tess_contour *contour)
  679. {
  680.     tess_contour *ptr;
  681.  
  682.     /* for all interiors of outer check if they are interior of contour */
  683.     /* if so, change that interior to exterior and move it of of the */
  684.     /* interior sequence */
  685.     if(outer->next!=NULL && outer->next->type==GLU_INTERIOR)
  686.     {
  687.         GLenum test;
  688.  
  689.         for(ptr=outer->next;ptr!=NULL && ptr->type==GLU_INTERIOR;ptr=ptr->next)
  690.         {
  691.             test=is_contour_contained_in(ptr,contour);
  692.             switch(test)
  693.             {
  694.                 case GLU_INTERIOR:
  695.                     /* contour is contained in one of the interiors */
  696.                     /* check if possibly contained in other exteriors */
  697.                     /* move ptr to first EXTERIOR */
  698.                     for(;ptr!=NULL && ptr->type==GLU_INTERIOR;ptr=ptr->next);
  699.                     if(ptr==NULL)
  700.                         /* another exterior */
  701.                         add_new_exterior(tobj,contour);
  702.                     else
  703.                         add_exterior_with_check(tobj,ptr,contour);
  704.                     return;
  705.                 case GLU_EXTERIOR:
  706.                     /* one of the interiors is contained in the contour */
  707.                     /* change it to EXTERIOR, and shift it away from the */
  708.                     /* interior sequence */
  709.                     shift_interior_to_exterior(tobj,ptr);
  710.                     break;
  711.                 case GLU_NO_ERROR:
  712.                     /* disjoint */
  713.                     break;
  714.                 default:
  715.                     abort();
  716.             }
  717.         }
  718.     }
  719.     /* add contour to the interior sequence */
  720.     add_new_interior(tobj,outer,contour);
  721. }
  722.  
  723. static void reverse_hierarchy_and_add_exterior(
  724.     GLUtriangulatorObj *tobj,
  725.     tess_contour *outer,
  726.     tess_contour *contour)
  727. {
  728.     tess_contour *ptr;
  729.  
  730.     /* reverse INTERIORS to EXTERIORS */
  731.     /* any INTERIORS? */
  732.     if(outer->next!=NULL && outer->next->type==GLU_INTERIOR)
  733.         for(ptr=outer->next;ptr!=NULL && ptr->type==GLU_INTERIOR;ptr=ptr->next)
  734.             ptr->type=GLU_EXTERIOR;
  735.     /* the outer now becomes inner */
  736.     outer->type=GLU_INTERIOR;
  737.     /* contour is the EXTERIOR */
  738.     contour->next=outer;
  739.     if(tobj->contours==outer)
  740.     {
  741.         /* first contour beeing reversed */
  742.         contour->previous=NULL;
  743.         tobj->contours=contour;
  744.     }
  745.     else
  746.     {
  747.         outer->previous->next=contour;
  748.         contour->previous=outer->previous;
  749.     }
  750.     outer->previous=contour;
  751. }
  752.  
  753. static void shift_interior_to_exterior(
  754.     GLUtriangulatorObj *tobj,
  755.     tess_contour *contour)
  756. {
  757.     contour->previous->next=contour->next;
  758.     if(contour->next!=NULL)
  759.         contour->next->previous=contour->previous;
  760.     else
  761.         tobj->last_contour=contour->previous;
  762. }
  763.  
  764. static void add_exterior_with_check(
  765.     GLUtriangulatorObj *tobj,
  766.     tess_contour *outer,
  767.     tess_contour *contour)
  768. {
  769.     GLenum test;
  770.  
  771.     /* this contour might be interior to further exteriors - check */
  772.     /* if not, just add as a new exterior */
  773.     for(;outer!=NULL && outer->type==GLU_EXTERIOR;outer=outer->next)
  774.     {
  775.         test=is_contour_contained_in(outer,contour);
  776.         switch(test)
  777.         {
  778.             case GLU_INTERIOR:
  779.                 /* now we have to check if contour is inside interiors */
  780.                 /* or not */
  781.                 /* any interiors? */
  782.                 if(outer->next!=NULL && outer->next->type==GLU_INTERIOR)
  783.                 {
  784.                     /* for all interior, check if inside any of them */
  785.                     /* if not inside any of interiors, its another */
  786.                     /* interior */
  787.                     /* or it may contain some interiors, then change */
  788.                     /* the contained interiors to exterior ones */
  789.                     add_interior_with_hierarchy_check(tobj,
  790.                         outer,contour);
  791.                 }
  792.                 else
  793.                 {
  794.                     /* not in interior, add as new interior contour */
  795.                     add_new_interior(tobj,outer,contour);
  796.                 }
  797.                 return;
  798.             case GLU_NO_ERROR:
  799.                 /* disjoint */
  800.                 break;
  801.             default:
  802.                 abort();
  803.         }
  804.     }
  805.     /* add contour to the exterior sequence */
  806.     add_new_exterior(tobj,contour);
  807. }
  808.  
  809. void tess_handle_holes(GLUtriangulatorObj *tobj)
  810. {
  811.     tess_contour *contour,*hole;
  812.     GLenum exterior_orientation;
  813.  
  814.     /* verify hole orientation */
  815.     for(contour=tobj->contours;contour!=NULL;)
  816.     {
  817.         exterior_orientation=contour->orientation;
  818.         for(contour=contour->next;
  819.             contour!=NULL && contour->type==GLU_INTERIOR;
  820.             contour=contour->next)
  821.         {
  822.             if(contour->orientation==exterior_orientation)
  823.             {
  824.                 tess_call_user_error(tobj,GLU_TESS_ERROR5);
  825.                 return;
  826.             }
  827.         }
  828.     }
  829.     /* now cut-out holes */
  830.     for(contour=tobj->contours;contour!=NULL;)
  831.     {
  832.         hole=contour->next;
  833.         while(hole!=NULL && hole->type==GLU_INTERIOR)
  834.         {
  835.             if(cut_out_hole(tobj,contour,hole)==GLU_ERROR)
  836.                 return;
  837.             hole=contour->next;
  838.         }
  839.         contour=contour->next;
  840.     }
  841. }
  842.  
  843. static GLenum cut_out_hole(
  844.     GLUtriangulatorObj *tobj,
  845.     tess_contour *contour,
  846.     tess_contour *hole)
  847. {
  848.     tess_contour *tmp_hole;
  849.     tess_vertex *v1,*v2,*tmp_vertex;
  850.     GLuint vertex1_cnt,vertex2_cnt,tmp_vertex_cnt;
  851.     GLuint i,j,k;
  852.     GLenum test;
  853.  
  854.     /* find an edge connecting contour and hole not intersecting any other */
  855.     /* edge belonging to either the contour or any of the other holes */
  856.     for(v1=contour->vertices , vertex1_cnt=contour->vertex_cnt , i=0;
  857.         i<vertex1_cnt;
  858.         i++ , v1=v1->next)
  859.     {
  860.         for(v2=hole->vertices , vertex2_cnt=hole->vertex_cnt , j=0;
  861.             j<vertex2_cnt;
  862.             j++ , v2=v2->next)
  863.         {
  864.             /* does edge (v1,v2) intersect any edge of contour */
  865.             for(tmp_vertex=contour->vertices , tmp_vertex_cnt=contour->vertex_cnt ,
  866.                     k=0;
  867.                 k<tmp_vertex_cnt;
  868.                 tmp_vertex=tmp_vertex->next , k++)
  869.             {
  870.                 /* skip edge tests for edges directly connected */
  871.                 if(v1==tmp_vertex || v1==tmp_vertex->next)
  872.                     continue;
  873.                 test=edge_edge_intersect(v1,v2,tmp_vertex,tmp_vertex->next);
  874.                 if(test!=GLU_NO_ERROR)
  875.                     break;
  876.             }
  877.             if(test==GLU_NO_ERROR)
  878.             {
  879.                 /* does edge (v1,v2) intersect any edge of hole */
  880.                 for(tmp_vertex=hole->vertices ,
  881.                         tmp_vertex_cnt=hole->vertex_cnt , k=0;
  882.                     k<tmp_vertex_cnt;
  883.                     tmp_vertex=tmp_vertex->next , k++)
  884.                 {
  885.                     /* skip edge tests for edges directly connected */
  886.                     if(v2==tmp_vertex || v2==tmp_vertex->next)
  887.                         continue;
  888.                     test=edge_edge_intersect(v1,v2,tmp_vertex,tmp_vertex->next);
  889.                     if(test!=GLU_NO_ERROR)
  890.                         break;
  891.                 }
  892.                 if(test==GLU_NO_ERROR)
  893.                 {
  894.                     /* does edge (v1,v2) intersect any other hole? */
  895.                     for(tmp_hole=hole->next;
  896.                         tmp_hole!=NULL && tmp_hole->type==GLU_INTERIOR;
  897.                         tmp_hole=tmp_hole->next)
  898.                     {
  899.                         /* does edge (v1,v2) intersect any edge of hole */
  900.                         for(tmp_vertex=tmp_hole->vertices ,
  901.                                 tmp_vertex_cnt=tmp_hole->vertex_cnt , k=0;
  902.                             k<tmp_vertex_cnt;
  903.                             tmp_vertex=tmp_vertex->next , k++)
  904.                         {
  905.                             test=edge_edge_intersect(v1,v2,tmp_vertex,
  906.                                 tmp_vertex->next);
  907.                             if(test!=GLU_NO_ERROR)
  908.                                 break;
  909.                         }
  910.                         if(test!=GLU_NO_ERROR)
  911.                             break;
  912.                     }
  913.                 }
  914.             }
  915.             if(test==GLU_NO_ERROR)
  916.             {
  917.                 /* edge (v1,v2) is good for eliminating the hole */
  918.                 if(merge_hole_with_contour(tobj,contour,hole,v1,v2)
  919.                     ==GLU_NO_ERROR)
  920.                     return GLU_NO_ERROR;
  921.                 else
  922.                     return GLU_ERROR;
  923.             }
  924.         }
  925.     }
  926.     /* other holes are blocking all possible connections of hole */
  927.     /* with contour, we shift this hole as the last hole and retry */
  928.     for(tmp_hole=hole;
  929.         tmp_hole!=NULL && tmp_hole->type==GLU_INTERIOR;
  930.         tmp_hole=tmp_hole->next);
  931.     contour->next=hole->next;
  932.     hole->next->previous=contour;
  933.     if(tmp_hole==NULL)
  934.     {
  935.         /* last EXTERIOR contour, shift hole as last contour */
  936.         hole->next=NULL;
  937.         hole->previous=tobj->last_contour;
  938.         tobj->last_contour->next=hole;
  939.         tobj->last_contour=hole;
  940.     }
  941.     else
  942.     {
  943.         tmp_hole->previous->next=hole;
  944.         hole->previous=tmp_hole->previous;
  945.         tmp_hole->previous=hole;
  946.         hole->next=tmp_hole;
  947.     }
  948.     hole=contour->next;
  949.     /* try once again - recurse */
  950.     return cut_out_hole(tobj,contour,hole);
  951. }
  952.  
  953. static GLenum merge_hole_with_contour(
  954.     GLUtriangulatorObj *tobj,
  955.     tess_contour *contour,
  956.     tess_contour *hole,
  957.     tess_vertex *v1,
  958.     tess_vertex *v2)
  959. {
  960.     tess_vertex *v1_new,*v2_new;
  961.  
  962.     /* make copies of v1 and v2, place them respectively after their originals */
  963.     if((v1_new=(tess_vertex *)malloc(sizeof(tess_vertex)))==NULL)
  964.     {
  965.         tess_call_user_error(tobj,GLU_OUT_OF_MEMORY);
  966.         return GLU_ERROR;
  967.     }
  968.     if((v2_new=(tess_vertex *)malloc(sizeof(tess_vertex)))==NULL)
  969.     {
  970.         tess_call_user_error(tobj,GLU_OUT_OF_MEMORY);
  971.         return GLU_ERROR;
  972.     }
  973.     v1_new->edge_flag=GL_TRUE;
  974.     v1_new->data=v1->data;
  975.     v1_new->location[0]=v1->location[0];
  976.     v1_new->location[1]=v1->location[1];
  977.     v1_new->location[2]=v1->location[2];
  978.     v1_new->x=v1->x;
  979.     v1_new->y=v1->y;
  980.     v1_new->shadow_vertex=v1;
  981.     v1->shadow_vertex=v1_new;
  982.     v1_new->next=v1->next;
  983.     v1_new->previous=v1;
  984.     v1->next->previous=v1_new;
  985.     v1->next=v1_new;
  986.     v2_new->edge_flag=GL_TRUE;
  987.     v2_new->data=v2->data;
  988.     v2_new->location[0]=v2->location[0];
  989.     v2_new->location[1]=v2->location[1];
  990.     v2_new->location[2]=v2->location[2];
  991.     v2_new->x=v2->x;
  992.     v2_new->y=v2->y;
  993.     v2_new->shadow_vertex=v2;
  994.     v2->shadow_vertex=v2_new;
  995.     v2_new->next=v2->next;
  996.     v2_new->previous=v2;
  997.     v2->next->previous=v2_new;
  998.     v2->next=v2_new;
  999.     /* link together the two lists */
  1000.     v1->next=v2_new;
  1001.     v2_new->previous=v1;
  1002.     v2->next=v1_new;
  1003.     v1_new->previous=v2;
  1004.     /* update the vertex count of the contour */
  1005.     contour->vertex_cnt += hole->vertex_cnt+2;
  1006.     /* remove the INTERIOR contour */
  1007.     contour->next=hole->next;
  1008.     if(hole->next!=NULL)
  1009.         hole->next->previous=contour;
  1010.     free(hole);
  1011.     /* update tobj structure */
  1012.     --(tobj->contour_cnt);
  1013.     if(contour->last_vertex==v1)
  1014.         contour->last_vertex=v1_new;
  1015.     /* mark two vertices with edge_flag */
  1016.     v2->edge_flag=GL_FALSE;
  1017.     v1->edge_flag=GL_FALSE;
  1018.     return GLU_NO_ERROR;
  1019. }
  1020.